In the related art, as a device which controls the travel of a vehicle, a device is known which generates a travel control plan and controls the travel of the vehicle on the basis of the generated travel control plan (for example, see Patent Literature 1). The device described in Patent Literature 1 generates the travel control plan (a travel locus pattern, a travel speed pattern, or the like) on the basis of road information or the like, evaluates the travel control plan on the basis of safety, comfort, mileage, or the like, and controls the vehicle on the basis of the travel control plan with excellent evaluation.